# 统计所有小于非负整数 n 的质数的数量。
#
#  示例:
#
#  输入: 10
# 输出: 4
# 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
#
#  Related Topics 哈希表 数学
#  👍 425 👎 0


# leetcode submit region begin(Prohibit modification and deletion)

# todo 搞懂优化思想
class Solution:
    def countPrimes(self, n: int) -> int:

        count = 0

        primes = [True] * n

        i = 2
        while i * i < n:

            j = i * i
            while j < n:
                primes[j] = False
                j += i
            i += 1

        for i in range(2, n):
            if primes[i]:
                count += 1
        return count


# leetcode submit region end(Prohibit modification and deletion)


print(Solution().countPrimes(1500000))
